package Solutions;

/***
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 *
 * 说明：
 *
 * 给定的 n 保证是有效的。
 *
 * 进阶：
 *
 * 你能尝试使用一趟扫描实现吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RemoveNthNode {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 删除链表的倒数第 n 个节点
     * @param head 链表的头节点
     * @param n 删除节点的位置
     * @return 新的链表的头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode pre, left, right;
        pre = right = left = head;
        for (int i = 0; i < n; i++) {
            // 先让右指针向后移动 n 个节点，如果没有移动到 n 次，说明，链表的长度不够，不存在倒数的第 n 个节点
            right = right.next;
            if (i != n - 1 && right == null)
                throw new RuntimeException("不存在需要删除的元素，请检查输入的数据是否正确。");
        }
        while (right != null) {// 移动右指针到链表的尾部，此时左指针所在的位置即为需要删掉的节点位置
            right = right.next;
            pre = left;
            left = left.next;
        }
        if (left == head) {// 如果删除的是头结点，将头结点后移一位，返回头结点即可
            head = head.next;
            return head;
        }
        pre.next = left.next;// 删除节点
        return head;// 返回头结点
    }

    /***
     * 执行结果：
     * 通过
     * 显示详情
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：36.8 MB, 在所有 Java 提交中击败了93.43% 的用户
     */
    public static void main(String[] args) {
        ListNode node0, node1, node2, node3, node4, head;
        node0 = new ListNode(0);
        node1 = new ListNode(1);
        node2 = new ListNode(2);
        node3 = new ListNode(3);
        node4 = new ListNode(4);
        node0.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node0;
        for (int i = 0; i < 5; i++) {
            if (i != 4) {
                System.out.print(head.val + "->");
            } else System.out.print(head.val + "\n");
            head = head.next;
        }
        head = node0;
        RemoveNthNode sol = new RemoveNthNode();
        head = sol.removeNthFromEnd(head, 3);
        for (int i = 0; i < 4; i++) {
            if (i != 3) {
                System.out.print(head.val + "->");
            } else System.out.print(head.val);
            head = head.next;
        }


    }
}
